package leetcode.editor.cn;

import java.util.logging.Level;

//[69]x 的平方根
public class Sqrtx69 {
    public static void main(String[] args) {
        Solution solution = new Sqrtx69().new Solution();
        int i = solution.mySqrtOrg(8);
//        int i = solution.mySqrt(2147395599);
        System.out.println("Sqrtx69:main:" + i);

    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {

        // TODO OK 执行函数
        //  执行耗时:1 ms,击败了94.52% 的Java用户
        //二分查找
        // 时间复杂度：O(logx)，即为二分查找需要的次数。
        // 空间复杂度：O(1)。
        // 省略小数：
        // 如果这个整数的平方 恰好等于 输入整数，那么我们就找到了这个整数；
        //
        // 如果这个整数的平方 【严格大于】 输入整数，那么这个整数肯定不是我们要找的那个数；
        //
        // 如果这个整数的平方 【严格小于】 输入整数，那么这个整数 可能 是我们要找的那个数（重点理解这句话）。
        public int mySqrt(int y) {
            //y [0,...]
            if (y <= 1) return y; //0 和 1 特殊值处理。

            int left = 1, right = y;
            int ans = left;
            while (left <= right) {//TODO 重点 等号。。。
                int mid = (right - left) / 2 + left;
                // 注意：这里为了避免乘法溢出，改用除法
                int i = y / mid;//此时。 eg: 5/2 = 2; 省略了小数。
                //如果这个整数的平方 【严格小于】 输入整数，那么这个整数 可能 是我们要找的那个数（重点理解这句话）。
                if (mid == i) {
                    //if double ..return ...res.. abs(mid^2 - y) < 0.00001
                    return mid;//结果
                } else if (mid > i) {// mid * mid >y
                    right = mid - 1; //结果，不可能大于，因为忽略了小数。
                } else {// mid * mid < y
                    ans = mid;////TODO 重点 ..可能是，结果因为。省略小数。
                    left = mid + 1;//当 省略小数时，left == right 跳出结果。
                }
            }
            return ans;
        }


        // 链接：https://leetcode.cn/problems/sqrtx/solution/x-de-ping-fang-gen-by-leetcode-solution/
        // 牛顿法
        //切线，代替 二分。
        //时间复杂度：O(logx)，此方法是二次收敛的，相较于二分查找更快。
        //空间复杂度：O(1)。
        public int mySqrtNiuDun(int x) {
            if (x == 0) {
                return 0;
            }

            double C = x, x0 = x;
            while (true) {
                double xi = 0.5 * (x0 + C / x0);
                if (Math.abs(x0 - xi) < 1e-7) {
                    break;
                }
                x0 = xi;
            }
            return (int) x0;
        }



        public int mySqrtOrg(int x) {
            int l = 0, r = x, ans = -1;
            while (l <= r) {
                int mid = l + (r - l) / 2;
                if ((long) mid * mid <= x) {
                    ans = mid;
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
            return ans;
        }


        // 链接：https://leetcode.cn/problems/sqrtx/solution/er-fen-cha-zhao-niu-dun-fa-python-dai-ma-by-liweiw/
        //
        // 思路分析
        //
        //从题目的要求和示例我们可以看出，这其实是一个查找整数的问题，并且这个整数是有范围的。
        //
        //如果这个整数的平方 恰好等于 输入整数，那么我们就找到了这个整数；
        //
        // 如果这个整数的平方 【严格大于】 输入整数，那么这个整数肯定不是我们要找的那个数；
        //
        // 如果这个整数的平方 【严格小于】 输入整数，那么这个整数 可能 是我们要找的那个数（重点理解这句话）。
        //
        // 因此我们可以使用「二分查找」来查找这个整数，不断缩小范围去猜。
        //
        //猜的数平方以后大了就往小了猜；
        //猜的数平方以后恰恰好等于输入的数就找到了；
        //猜的数平方以后小了，可能猜的数就是，也可能不是。
        //很容易知道，题目要我们返回的整数是有范围的，直觉上一个整数的平方根肯定不会超过它自己的一半，但是
        //0 和 1 除外，因此我们可以在
        //1 到输入整数除以 2 这个范围里查找我们要找的平方根整数。
        //0 单独判断一下就好。
        //
        //作者：liweiwei1419
        //链接：https://leetcode.cn/problems/sqrtx/solution/er-fen-cha-zhao-niu-dun-fa-python-dai-ma-by-liweiw/
        //来源：力扣（LeetCode）
        //著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
        public int mySqrtLiWeiWei(int x) {
            // 特殊值判断
            if (x == 0) {
                return 0;
            }
            if (x == 1) {
                return 1;
            }

            int left = 1;
            int right = x / 2;
            // 在区间 [left..right] 查找目标元素
            while (left < right) {
                int mid = left + (right - left + 1) / 2;
                // 注意：这里为了避免乘法溢出，改用除法
                if (mid > x / mid) {
                    // 下一轮搜索区间是 [left..mid - 1]
                    right = mid - 1;
                } else {
                    // 下一轮搜索区间是 [mid..right]
                    left = mid;
                }
            }
            return left;
        }


    }
//leetcode submit region end(Prohibit modification and deletion)

}